package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import lombok.AccessLevel;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.*;

/**
 * <h1>Kosaraju-强联通分量算法</h1>
 * <p>
 *     <h2>强联通分量</h2>
 *     <p>
 *         在图中，某些分量中，存在s-v的路径，也存在v-s的路径。这个分量表示强连通分量
 *     </p>
 * </p>
 * <p>
 *     Kosaraju的算法核心步骤是对图G进行普通的连通分量计算。计算的顺序是<span>G<sup>R<sup/></span>   的reverseOrder。
 * </p>
 * <p>
 *    <h2>命题</h2>
 *    <p>
 *        使用深度优先搜索查找给定有向图 G 的反向图 <span>G<sup>R<sup/></span>
 *
 *        根据由此得到的所有顶点的逆后 序再次用深度优先搜索处理有向图 G（Kosaraju 算法），其构造函数中的每一次递归调用所标 记的顶点都在同一个强连通分量之中。
 *    </p>
 *    <h2>证明</h2>
 *    <p>
 *          首先要用反证法证明“<b>每个和 s 强连通的顶点 v 都会在构造函数调用的 dfs(G,s)</b> 中 被访问到”。
 *          假设有一个和 s 强连通的顶点 v 不会在构造函数调用的 dfs(G,s) 中被访问到。
 *          因为存在从 s 到 v 的路径，所以 v 肯定在之前就已经被标记过了。
 *          但是，因为也存在从 v 到 s 的路径，在 dfs(G,v)
 *          调用中 s 肯定会被标记，因此构造函数应该是不会调用 dfs(G,s) 的。 矛盾。<br><br>
 *
 *          <b>这里可以证明 s -----v。同时对于<span>G<sup>R<sup/></span>,存在v-----s.下面会用到重要.[证明1]</b><br><br>
 *
 *
 *          其次，要证明“<b>构造函数调用的 dfs(G,s) 所到达的任意顶点 v 都必然是和 s 强连通的</b>”。
 *          设 v 为 dfs(G,s) 到达的某个顶点。那么，G 中必然存在一条从 s 到 v 的路径，
 *          因此只需要证 明 G 中还存在一条从 v 到 s 的路径即可。这也等价于 <span>G<sup>R<sup/></span> 中存在一条从 s 到 v 的路径，因此只 需要证明在 GR 中存在一条从 s 到 v 的路径即可。<br><br>
 *
 *
 *          证明的核心在于，按照逆后序进行的深度优先搜索意味着，在<span>G<sup>R<sup/></span>中进行的深度优先搜索中， dfs(G,v) 必然在 dfs(G,s) 之前就已经结束了，这样 dfs(G,v) 的调用就只会出现两种 情况：
 *          <ul>
 *              <li>先调用dfs(v),在dfs(v)完全执行完毕，包括dfs(v)内部的dfs(*)结束之后，在调用dfs(s)。(拓扑排序的功能参见{@link DfsOrder})</li>
 *              <li>调用在 dfs(s),在dfs(s)的内部dfs递归中，调用dfs(v)</li>
 *          </ul>
 *          第一种情况是不可能出现的，因为在 <span>G<sup>R<sup/></span> 中存在一条从 v 到 s 的路径，见[证明1]；<br/>
 *          而第二种情况则说明 <span>G<sup>R<sup/></span> 中存在一条从 s 到 v 的路径。证毕。
 *    </p>
 * </p>
 */
public class KosarajuStrongConnectedComponent<T> {


    @Setter(AccessLevel.PRIVATE)
    @Accessors(chain = true)
    private Graph<T> graph;
    /**
     * 顶点所属的连通分量的标记
     */
    private Map<Vertex<T>,Integer> connectedComponentMark = new HashMap();
    /**
     * 连通分量的值
     */
    private int connectedComponentNum = 0;

    /**
     * 已经访问过
     */
    private Set<Vertex<T>> accessed = new HashSet<>();







    public Integer countOfConnectedComponent(){
        return connectedComponentNum + 1;
    }
    public boolean isStrongConnected(Vertex<T> s,Vertex<T> v){
        return Objects.equals(connectedComponentMark.get(s),connectedComponentMark.get(v));
    }









    private KosarajuStrongConnectedComponent<T> init(){

        DfsOrder.create( graph.reverse()).getReversePost().forEach(item->{
            if(accessed.contains(item)){
                return;
            }
            dfs(graph.getVertices().get(item));
            connectedComponentNum++;
        });
        return this;
    }


    private void dfs(Vertex<T> vertex){
        accessed.add(vertex);
        connectedComponentMark.put(vertex, connectedComponentNum);

        vertex.getNext().forEach(item->{
            if(!accessed.contains(item.getTo())){
                dfs(item.getTo());
            }
        });

    }

    public static final <TT> KosarajuStrongConnectedComponent<TT> create(Graph<TT> graph){
        return new KosarajuStrongConnectedComponent<TT>().setGraph(graph).init();
    }


}
